#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>


// FUNCTION: 定义动态数组
typedef int ElemType;

typedef struct {
	ElemType *elem;//存储元素的起始地址
	int TableLen;//元素个数
} SSTable;


// FUNCTION: 随机数生成
void ST_Init(SSTable &ST, int len) {
	// NOTE: 变量初始化
	// STEP: 确定表长
	ST.TableLen = len;

	// STEP: 申请动态数组实际空间
	ST.elem = (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);

	// STEP: 存放赋值变量是的索引
	int i;


	// NOTE: 生成随机数
	srand(time(NULL));


	// NOTE: 将数据存储到数组中
	// HINT: 为啥这里零号位置也存放了随机了数据？是为折半查找服务的。
	for (i = 0; i < ST.TableLen; i++) {
		ST.elem[i] = rand() % 100;
	}
}


// FUNCTION: 输出数组中全部元素
void ST_print(SSTable ST) {
	for (int i = 0; i < ST.TableLen; i++) {
		printf("%3d", ST.elem[i]);
	}

	printf("\n");
}


// FUNCTION: 实现交换
void swap(ElemType &a, ElemType &b) {
	ElemType tmp;
	tmp = a;
	a = b;
	b = tmp;
}


// FUNCTION: 冒泡排序
// 原始数据：64 94 95 79 69 84 18 22 12 78
// 原始数据：12 18 22 64 69 78 79 84 94 95
void BubbleSort(ElemType A[], int n) {
	// NOTE: 变量初始化
	// STEP: 待排数组元素索引
	int i, j;

	// STEP: 发生交换标记位（熔断标记）
	// HINT: 初值设置为false。如果冒泡排序中，两元素发生了交换，就将其设置为true某次再某次比较后再也没有发生任何的元素交换。那么可以认为在此处之后的数据已经有序了，所以可以熔断后续操作，加速程序执行。
	bool flag;


	// NOTE: 进行冒泡排序（按从小到大排序）
	// HINT: 因为长度为n的数组，最多只需要n-1次
	for (i = 0; i < n - 1; ++i) {
		// STEP: 初始化发生交换标记位
		flag = false;

		// STEP: 每轮逐个元素进行比较
		for (j = n - 1; j > i; --j) {
			// HINT: 实现按从小到大达排序
			if (A[j - 1] > A[j]) {
				// 实现交换
				swap(A[j - 1], A[j]);

				// 将标记位设置为true
				flag = true;
			}
		}

		// STEP: 某轮比较中，
		if (!flag)
			return;
	}
}



//《王道C督学营》课程
//冒泡排序
int main() {
	setbuf(stdout, NULL);


	// NOTE: Variable declaration
	// STEP: 声明动态数组
	SSTable ST;

	// STEP: 声明一组数
	ElemType A[10] = {64, 94, 95, 79, 69, 84, 18, 22, 12, 78};


	// NOTE: 数组元素赋值
	ST_Init(ST, 10);

	// STEP: 数组元素重新赋值（方便填充）
	// REVIEW: 此段代码目的是：在ST_Init执行结束后，ST虽已经初始化，但其中的数据都是随机数，不方便检查程序是否有bug。为了欲使检查变得方便，使用memcpy将自己定义的数组A直接覆盖ST的elem区域。
	// HINT: 内存copy接口。当你copy整型数组，或者浮点型时，要用memcpy。
	// ALERT: 注意区分memcpy和strcpy的区别。
	memcpy(ST.elem, A, sizeof(A));

	printf("Original sequence is: ");
	ST_print(ST);


	// NOTE: 冒泡排序
	BubbleSort(ST.elem, 10);
	printf("After sorting, sequence is: ");
	ST_print(ST);

	// NOTE: 快速排序
	// QuickSort(ST.elem, 0, 9);
	// printf("After sorting, sequence is: ");
	// ST_print(ST);


	return 0;
}